Retrieving a route or finding a way to or from a destination and visualizing the route are very important functions in a variety of applications including, for example, firefighting, evacuation for disaster, travel guiding, and building security. For example, in firefighting, it is necessary for a fire fighter to retrieve an optimal route to a fire location according to current conditions including, for example, shortest path, smoke density, temperature, closed fire shutters, people presence and density, locked doors, etc. Similarly, it is necessary for occupants of a building to find the best emergency route to evacuate the building to avoid, for example, a fire, a crime scene, or a terrorism incident.
In the application of travel guiding, for example, a building security system can necessitate retrieving a route in a building. Different visitors can have different privileges allowing them to walk in different zones of a building. Accordingly, it is necessary for different visitors to be able to retrieve a route to their respective destinations based on their respective privileges.
More examples of applications in which route retrieval is advantageous include determining a route to a safe haven for occupants of a building when a disaster such as a fire, crime, or terrorism occurs and determining a route for a medial first responder to reach a victim.
Methods to establish routes to and from a region are known in the art. For example, U.S. Publication No. 2005/0128070 to Faltesek et al. entitled “Building Emergency Path Finding Systems and Method,” which is assigned to the assignee hereof and is hereby incorporated by reference, discloses a method to establish ingress and egress paths to and from a region by evaluating signals from a plurality of detectors. However, when conditions in the region and surrounding area change, it is desirable to establish updated routes to and from the region.
Accordingly, it is advantageous for route retrieval to occur in real time because the status of a building can vary over time. For example, the temperature and smoke density at a particular location in a building can change as fire and smoke spread in the building. Additionally, the number of evacuees on a particular route in a building may vary as the evacuees move towards exits. Furthermore, the connectivity between different zones in a building can change from time to time when, for example, fire doors are closed when a fire hazard exists, doors are locked due to security privileges, or floor plans are altered.
Other reasons for route retrieval to occur in real time include the presence or absence of emergency personnel at particular locations, movement of targeted individuals, and the presence of obstacles, for example, as detected by video sensors.
U.S. Publication No. 2007/0279210 to Li et al. entitled “Time-Dependent Classification and Signaling of Evacuation Route Safety,” which is assigned to the assignee hereof and is hereby incorporated by reference, discloses an adaptive evacuation system and method for providing a safety route for evacuees. Li et al. discloses using sensors to evaluate whether a path is safe or unsafe. However, it is desirable to build a weighted graph to retrieve an optimal route within a region.
Weighted graphs to retrieve an optimal route are known in the art. However, weighted graphs have not previously been updated in real time based on changing conditions. As explained above, it is advantageous for route retrieval to occur in real time because the status of a building can vary over time. There is thus a continuing, on going need for a method and system to determine a route to a particular destination in real time. Preferably, such methods and systems generate a weighted graph, update the weighted graph in real time to account for changing conditions, and compute an optimal path between particular locations represented on the weighted graph.